use std::vec;

// 1. 计数排序
pub fn counting_sort(a: &Vec<i32>, b: &mut Vec<i32>, k: i32) {
    println!("{:?}", a);
    let mut c: Vec<i32> = vec![0; k as usize];
    let mut id: usize;
    for i in 0..a.len() {
        id = a[i] as usize;
        c[id] += 1;
    }
    println!("{:?}", c);
    for i in 1..(k as usize) {
        c[i] += c[i - 1];
    }
    println!("{:?}", c);
    for i in (0..a.len()).rev() {
        id = a[i] as usize;
        b[(c[id] as usize) - 1] = a[i];
        c[id] -= 1;
    }
    println!("{:?}", b);
}

// 2. 基数排序
// 子过程-计数排序（稳定性）
pub fn sub_radix_sort(a: &Vec<i32>, b: &mut Vec<i32>, c: &Vec<i32>, k: i32) {
    let mut d: Vec<i32> = vec![0; k as usize];
    let mut id: usize;
    for i in 0..a.len() {
        id = a[i] as usize;
        d[id] += 1;
    }
    for i in 1..(k as usize) {
        d[i] += d[i - 1];
    }
    for i in (0..a.len()).rev() {
        id = a[i] as usize;
        b[d[id] as usize - 1] = c[i];
        d[id] -= 1;
    }
}
pub fn radix_sort(v: &Vec<i32>, d: i32, k: i32) -> Vec<i32> {
    let mut a: Vec<i32>;
    let mut b = v.clone();
    let mut temp = v.clone();
    for i in 0..(d as u32) {
        a = b.iter().map(|x| *x / (10_i32.pow(i)) % 10).collect();
        println!("{:?}", a);
        sub_radix_sort(&a, &mut b, &temp, k);
        temp = b.clone();
        println!("{:?}", b);
    }
    b
}

// 3. 桶排序
pub fn bucket_sort(a: &Vec<f32>) -> Vec<f32> {
    let n = a.len();
    let div = 1. / n as f32;
    let mut b = vec![vec![0_f32; 0]; n];
    let mut id: usize;
    for i in 0..n {
        id = (a[i] / div) as usize;
        b[id].push(a[i]);
        for j in (0..(b[id].len() - 1)).rev() {
            if a[i] < b[id][j] {
                b[id].swap(j, j + 1);
            } else {
                break;
            }
        }
    }
    for i in 0..n {
        println!("{:?}", b[i]);
    }
    b.into_iter().flatten().collect::<Vec<f32>>()
}
